package oop.ex4.crosswords.strategies;

import java.io.IOException;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;
import java.util.Set;
import java.util.SortedSet;
import java.util.TreeSet;

import oop.ex4.crosswords.CrosswordDictionary;
import oop.ex4.crosswords.CrosswordEntry;
import oop.ex4.crosswords.CrosswordPosition;
import oop.ex4.crosswords.MyCrossword;
import oop.ex4.crosswords.MyCrosswordDictionary;
import oop.ex4.crosswords.MyCrosswordEntry;
import oop.ex4.crosswords.MyCrossword.CrosswordSquare;

/**
 * The small grid strategy. <br>
 * In case there are more terms then entries then does an entries based search.
 * @author yomach
 * @author mbattat
 */
public class SmallGridCrosswordStrategy extends CrosswordStrategy {

	///////////////////////////////////////////////////////
	////////////////////////Constants//////////////////////
	///////////////////////////////////////////////////////

	/**
	 * The strategy's rating.
	 */
	private static final int STRATEGY_RATING = 5;

	///////////////////////////////////////////////////////
	//////////////////////Data Members/////////////////////
	///////////////////////////////////////////////////////

	/**
	 * The dictionary.
	 */
	protected PatternBasedExtendedCrosswordDictionary _dict;

	///////////////////////////////////////////////////////
	//////////////////////Constructors/////////////////////
	///////////////////////////////////////////////////////

	/** 
	 * A constructor that sets the board to the SmallGrid strategy.
	 * @param board The board.
	 * @param dict The dictionary.
	 */
	public SmallGridCrosswordStrategy() {
		super();
	}

	///////////////////////////////////////////////////////
	/////////////////////Public Methods////////////////////
	///////////////////////////////////////////////////////

	@Override
	public void initializeStrategy(CrosswordDictionary dict, CrosswordSquare[][] board) {
		super.initializeStrategy(dict, board);	
		int entrySum = 0;
		int longstEntryLength = _entriesList.longestEntryLength();
		int shortestWordLength = _dict.shortestWordLength();
		for (int i = shortestWordLength ; i <= longstEntryLength; i++) {
			for (CrosswordEntry entry : _entriesList.getSet(i)) {
				entrySum += _entriesList.getEntryLength(entry);  // Add the length of the entry for the quality bound.
				CrosswordPosition pos = entry.getPosition();
				_board[pos.getX()][pos.getY()].setQualityBound(pos.isVertical(), _entriesList.getEntryLength(entry)); // Update the local quality bound.
			}
		}
		_bestQuality = _qualityBound = entrySum;
	}

	@Override
	public void doMove(CrosswordEntry move) {
		super.doMove(move);
		calculateQualityBound(move);
	}

	@Override
	public void undoMove(CrosswordEntry move) {
		super.undoMove(move);
		calculateQualityBound(move);
	}

	@Override
	public Iterator<CrosswordEntry> getMoveIterator() {
		return new SmallGridMovesIterator();
	}

	@Override
	public int isGoodStrategy(CrosswordDictionary dict,
			CrosswordSquare[][] board) {
		_dict = new PatternBasedExtendedCrosswordDictionary(dict);
		super._dict = _dict;
		if (getValidTermNum(board) >= getValidEntryNum(board)) { return STRATEGY_RATING; }
		return 0;
	}

	///////////////////////////////////////////////////////
	////////////////////Private Methods////////////////////
	///////////////////////////////////////////////////////

	/**
	 * Calculates the new quality bound.
	 * @param move The move to calculate the quality bound from.
	 */
	private void calculateQualityBound(CrosswordEntry move) {
		CrosswordPosition pos = move.getPosition();
		int x = pos.getX();
		int y = pos.getY();
		boolean vertical = pos.isVertical();
		String term = move.getTerm();
		int length = term.length();
		int startOfWord = (vertical ? y : x);
		int endOfWord = startOfWord + length - 1;
		for (int i = endOfWord; i >= 0; i--) { // For the squares that are parallel as the newly added word.
			CrosswordSquare square = _board[(vertical ? x : i)][vertical ? i : y];
			if (square == null) { break; }
			updateSquareQualityBound(square, vertical);
		}
		for (int i = endOfWord; i >= startOfWord; i--) { // For the square that are perpendicular to the newly added word.
			for (int j = vertical ? x : y; j >= 0; j--) {
				CrosswordSquare square = _board[(vertical ? j : i)][vertical ? i : j];
				if (square == null) { break; }
				updateSquareQualityBound(square, !vertical);
			}
		}
	}

	/**
	 * Calculates the new quality bound for the entry at the given square.
	 * If there was a change in the quality bound, updates _qualityBound.
	 * @param square The square.
	 * @param vertical Update for the vertical entry or horizontally entry.
	 */
	private void updateSquareQualityBound(CrosswordSquare square, boolean vertical) {
		int old = square.getQualityBound(vertical);
		int difference = 0;
		int entryLength = square.getEntryLength(vertical);
		String nextTerm = null;
		boolean found = false;
		if (square.getEntry(vertical).getTerm() != null) { // There's a term there.
			difference = (old - square.getEntry(vertical).getLength()); 
		}
		else if (entryLength >= _dict.shortestWordLength()) { // If there are words short enough.
			for (int i = _dict.shortestWordLength(); i <= Math.min(_dict.longestWordLength(), entryLength) && !found; i++) { // For all of them.
				Iterator<String> termIterator = _dict.findMatchingWords(String.valueOf(square.getCharsAround(vertical)).substring(0, entryLength + _dict.shortestWordLength() - i)).iterator();
				while (termIterator.hasNext()){
					nextTerm = termIterator.next();
					if (_dict.getUsedTermsList(nextTerm.length()).contains(nextTerm)) {// If the word is used or doesn't fit, continue.
						continue; 
					}
					else {
						found = true; // If it fits, break.
						break;
					}
				}
			}
			if (found) { difference = (old - entryLength);	} // Difference if found.
			else { difference = old; } // Difference if not found.
		} else { difference = old; } 
		if (difference != 0) {
			_qualityBound -= difference; // Update quality bound.
			square.setQualityBound(vertical, old - difference);
		}
	}

	/**
	 * A nested decorator dictionary class that implements the ExtendedCrosswordDictionary.
	 * It's meant to be used with other simple dictionary implementation. <br>
	 * This class supports finding of words that match a given pattern as defined 
	 * in {@link MyCrossword.CrosswordSquare} in O(n) where n is the 
	 * number of words with this length in the dictionary (with very low 
	 * constants, much closer to o(m) where m is the number of words to return).
	 * @author yomach
	 * @author mbattat
	 */
	private class PatternBasedExtendedCrosswordDictionary implements ExtendedCrosswordDictionary {

		///////////////////////////////////////////////////////
		////////////////////////Constants//////////////////////
		///////////////////////////////////////////////////////

		/**
		 * A string that contains the ABC by order.
		 */
		protected static final String ABC = "abcdefghijklmnopqrstuvwxyz-";

		///////////////////////////////////////////////////////
		//////////////////////Data Members/////////////////////
		///////////////////////////////////////////////////////

		/**
		 * A basic implementation of a dictionary.
		 */
		protected CrosswordDictionary _simpleDictionary;

		/**
		 * The extended dictionary.
		 */
		protected ArrayList<List<List<SortedSet<String>>>> _extendedDictionary;

		/**
		 * A set that holds all of the used terms.
		 */
		protected ArrayList<HashSet<String>> _usedTerms;

		///////////////////////////////////////////////////////
		//////////////////////Constructors/////////////////////
		///////////////////////////////////////////////////////

		/**
		 * Constructs a new dictionary based on a the given dictionary.
		 * @param dictionary The dictionary.
		 */
		public PatternBasedExtendedCrosswordDictionary (CrosswordDictionary dictionary) {
			_simpleDictionary = dictionary;
			createExtendedDictionary();
		}

		///////////////////////////////////////////////////////
		/////////////////////Public Methods////////////////////
		///////////////////////////////////////////////////////

		/**
		 * Returns all the words that match the given pattern. <p>
		 * The pattern is as defined in {@link MyCrossword.CrosswordSquare} <br>S
		 * Note that it'll only return words that have the exact length as the given pattern. <br>
		 * The set returned will not be affected by changes in the dictionary and likewise
		 * changes in the set will not affect the dictionary. <br>
		 * The words returned will be sorted lexicography.
		 * @param pattern The pattern.
		 * @return All possible words that fit the pattern.
		 * @see MyCrossword.CrosswordSquare
		 */
		public SortedSet<String> findMatchingWords(CharSequence pattern) {
			int length = pattern.length();
			// If the pattern is empty return all words with the same length.
			int firstCharLocation = firstCharLocation(pattern);
			if (firstCharLocation == -1) { return findMatchingWords(length); }
			// Else set it to be all the words that match the first char in the sequence.
			SortedSet<String> matchingWords = new TreeSet<String>(_extendedDictionary.get(length-2).get(firstCharLocation).get(ABC.indexOf(pattern.charAt(firstCharLocation))));
			// This loop Checks if one or more of the char's in the sequence is not an empty
			// space. If it is not, it gets all the possible words that it contains 
			// and retain it with the words that matched the filter until now.
			for (int i = firstCharLocation+1; i < length; i++){
				if (pattern.charAt(i) != SPACE && length-2 < _extendedDictionary.size()) {
					matchingWords.retainAll(_extendedDictionary.get(length-2).get(i).get(ABC.indexOf(pattern.charAt(i))));
					if (matchingWords.size() == 0) { break; }
				}
			}
			return matchingWords;
		}

		/**
		 * Returns all the words are at the given length. <br>
		 * The set returned will not be affected by changes in the dictionary and likewise
		 * changes in the set will not affect the dictionary. <br>
		 * The words returned will be sorted lexicography.
		 * @param length The length of the word.
		 * @return All of the words with the given length.
		 */
		public SortedSet<String> findMatchingWords(int length) {
			return new TreeSet<String>(_extendedDictionary.get(length-2).get(length).get(0));
		}

		@Override
		public String getTermDefinition(String term) {
			return _simpleDictionary.getTermDefinition(term);
		}

		@Override
		public Set<String> getTerms() {
			return _simpleDictionary.getTerms();
		}

		@Override
		public void load(String dictFileName) throws IOException {
			_simpleDictionary = new MyCrosswordDictionary(dictFileName); // Creates the simple dictionary.
			createExtendedDictionary();
		}

		public boolean markAsUsed(String term) {
			return _simpleDictionary.getTerms().contains(term) ?
					_usedTerms.get(term.length()-2).add(term) :
						false;
		}

		@Override
		public boolean markAsUnused(String term) {
			return _usedTerms.get(term.length()-2).remove(term);
		}

		@Override
		public Set<String> getUsedTermsList(int length) {
			return _usedTerms.get(length-2);
		}

		@Override
		public int longestWordLength() {
			for (int i = _extendedDictionary.size()-1; i >= 0; i--) {
				if (_extendedDictionary.get(i).get(i+2).get(0).size() - _usedTerms.get(i).size() > 0) { return i+2; }
			}
			return -1; // Dictionary is empty. 
		}

		@Override
		public int shortestWordLength() {
			for (int i = 0; i < _extendedDictionary.size(); i++) {
				if (_extendedDictionary.get(i).get(i+2).get(0).size() - _usedTerms.get(i).size() > 0) { return i+2; }
			}
			return 0; // Dictionary is empty. 
		}

		///////////////////////////////////////////////////////
		/////////////////////Private Methods///////////////////
		///////////////////////////////////////////////////////

		/**
		 * Returns the index of the first occurrence of a character that is not space. <br>
		 * If all of the characters are spaces, returns -1.
		 * @param string The charSequance.
		 * @return The index of the first occurrence of a character that is not space. 
		 */
		private int firstCharLocation(CharSequence string) {
			for (int i=0; i<string.length(); i++) {
				if (string.charAt(i) != SPACE) { return i; }
			}
			return -1;
		}

		/**
		 * Creates the extended dictionary.
		 */
		private void createExtendedDictionary() {
			Iterator<String> iterator = _simpleDictionary.getTerms().iterator();
			int maxLength = findLongestWord();
			// Creates the extended dictionary database, contains words from length 2+.
			_extendedDictionary = new ArrayList<List<List<SortedSet<String>>>>(maxLength-1); 
			_usedTerms = new ArrayList<HashSet<String>>(maxLength-1);
			for (int i = 0; i < maxLength-1; i++){
				// A new list for every letter in the word and 1 for all the words in this size.
				_extendedDictionary.add(i, new ArrayList<List<SortedSet<String>>>(i+3)); 
				for (int j=0; j < i+2; j++){
					// Creates an array list with ABC.length() (26) set's.
					_extendedDictionary.get(i).add(j, new ArrayList<SortedSet<String>>(ABC.length()));
					for (int k=0; k < ABC.length(); k++) {
						// Creates an empty set for every ABC letter.
						_extendedDictionary.get(i).get(j).add(k, new TreeSet<String>());					
					}
				}
				// Creates the array list and set for all words in this length.
				_extendedDictionary.get(i).add(i+2, new ArrayList<SortedSet<String>>(1));
				_extendedDictionary.get(i).get(i+2).add(0, new TreeSet<String>());
				_usedTerms.add(i, new HashSet<String>());
			}
			iterator = _simpleDictionary.getTerms().iterator();
			while (iterator.hasNext()){    
				// Adds all the word's in the simple dictionary to
				// The extended dictionary
				String word = iterator.next();
				int length = word.length();
				for (int i = 0; i < length; i++) {
					_extendedDictionary.get(length-2).get(i).get(ABC.indexOf(word.charAt(i))).add(word);
				}
				// Adds the word to the global list of words in this length.
				_extendedDictionary.get(length-2).get(length).get(0).add(word);
			}
		}

		/**
		 * Find and returns the length of the longest word in the dictionary by iterating over it.
		 * @return The length of the longest word.
		 */
		private int findLongestWord() {
			int maxLength = 0;
			for (String word : _simpleDictionary.getTerms()){
				if (word.length() > maxLength) { maxLength = word.length();}
			}
			return maxLength;
		}

	}

	/**
	 * A nested Iterator that iterate over all possible moves by a specific Strategy.
	 * @author yomach
	 * @author mbattat
	 */
	private class SmallGridMovesIterator extends MovesIterator{

		/**
		 * The current entry pattern.
		 */
		private String _entryPattern;		

		/**
		 * An Iterator that iterate over the entries in the crossword.
		 */
		private Iterator<CrosswordEntry> _entryIterator;

		/**
		 * An Iterator that iterate over the possible terms.
		 */
		private Iterator<String> _termIterator;

		/**
		 * The current entry length.
		 */
		private int _currentEntryLength;

		/**
		 * The current entry position.
		 */
		private CrosswordPosition _pos;

		/**
		 * The current entry.
		 */
		private CrosswordEntry _currentEntry;

		///////////////////////////////////////////////////////
		//////////////////////Constructors/////////////////////
		///////////////////////////////////////////////////////

		/**
		 * Constructs a new MoveIterator in a certain strategy.
		 */
		public SmallGridMovesIterator() {
			super();
			_currentEntryLength = _maxFit + 1; // In the createNextMove the first iteration lowers it by one.
		}

		///////////////////////////////////////////////////////
		////////////////////Private Methods////////////////////
		///////////////////////////////////////////////////////

		/**
		 * {@inheritDoc} <br>
		 * Small Grid strategy - checks every entry from largest to smallest, 
		 * and tries to fit every word from largest to smallest. 
		 * @return The next move.
		 */
		protected CrosswordEntry createNextMove() {
			if (_currentEntryLength <= _minFit) {
				return null;
			}
			while ((_entryIterator == null || !_entryIterator.hasNext()) && _currentEntryLength > _minFit) {
				if ((_termIterator != null && _termIterator.hasNext()) 
						|| (_entryPattern != null && _entryPattern.length() >= _minFit)) { break; }
				_entryIterator =  _entriesList.getIterator(--_currentEntryLength);
				_termIterator = null;
			}
			while ((_termIterator == null || !_termIterator.hasNext()) && _entryIterator.hasNext() 
					&& (_entryPattern == null || _entryPattern.length() < _minFit)) {
				_currentEntry = _entryIterator.next();
				if (!_entriesList.getUsedEntriesSet(_currentEntryLength).contains(_currentEntry)) {
					_pos = _currentEntry.getPosition();
					_entryPattern = String.valueOf(_board[_pos.getX()][_pos.getY()].getCharsAround(_pos.isVertical()));
					break;
				}
				_currentEntry = null;
			}
			if (_currentEntry == null) { return createNextMove(); }
			while ((_termIterator == null || !_termIterator.hasNext()) 
					&& _entryPattern.length() >= _minFit) {
				_termIterator = _dict.findMatchingWords(_entryPattern).iterator();
				_entryPattern = _entryPattern.substring(0, _entryPattern.length() - 1);
			}
			String nextTerm;
			while (_termIterator.hasNext()) {
				nextTerm = _termIterator.next();
				if (!_dict.getUsedTermsList(nextTerm.length()).contains(nextTerm)){
					return new MyCrosswordEntry(nextTerm, _dict, _pos);
				}
			}
			return createNextMove();
		}
	}
}